package com.mrzhou.study.struct.array;

/**
 * 数组环状队列:
 *  以下代码是个人在思考环形队列的特点是写的; 和教学文档上的有差距
 *  教学文档通过将rear和front换了一种描述, 并且通过取模的方式决定队列是否已满(个人通过增加size变量来决定)
 *  文档实现的思路见: classpath: doc/Java数据结构和算法.pdf ~ 3.2.3数组模拟队列思路
 */
public class QueueAround<T> {

    private Object[] queue; // 队列
    private int maxSize; // 队列的最大容量
    private int size; // 队列中未处理的元素大小
    private int rear; // 尾部指针
    private int front; // 头部指针

    public QueueAround(int size) {
        maxSize = size;
        this.queue = new Object[size];
        this.size = 0;
        this.front = -1;
        this.rear = -1;
    }


    public void add(T t) throws Exception {
        if(isFull()) {
            throw new Exception("队列已满");
        }
        if(rear == maxSize -1 && front != -1) {
            rear = -1;
        }
        rear++; // 尾部指针后移
        size++; // 队列中元素数量+1
        queue[rear] = t;
    }

    public T get() throws Exception {
        if(isEmpty()) {
            throw new Exception("队列为空");
        }

        if(front == maxSize -1 && rear != -1) {
            front = -1;
        }
        front++;
        size--;
        return (T) queue[front];
    }

    /**
     * 通过size是否和队列的最大容量是否相等来判断队列是否已满
     * @return
     */
    public boolean isFull() {
        return size == maxSize;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return this.size;
    }

    /** 查看环形队列中的有效元素 */
    public String showQueue() {
        StringBuffer sb = new StringBuffer("[");
        int temp = front;
        for(int i =0; i < size; i++) {
            if(temp == maxSize - 1) {
                temp = -1;
            }
            temp++;
            if(i == size-1) {
                sb.append(queue[temp]);
            } else {
                sb.append(queue[temp] + ",");
            }
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) throws Exception {
        QueueAround<String> queue = new QueueAround<>(4);
        queue.add("0");
        queue.add("1");
        queue.add("2");
        System.out.println("第一次" + queue.showQueue());
        System.out.println(queue.get());
        System.out.println("第二次" + queue.showQueue());
        System.out.println(queue.get());
        System.out.println("第三次" + queue.showQueue());
        queue.add("3");
        queue.add("4");
        queue.add("5");
        System.out.println("第四次" + queue.showQueue());
        System.out.println(queue.get());
        System.out.println("第五次" + queue.showQueue());
        System.out.println(queue.get());
        System.out.println(queue.get());
        System.out.println(queue.get());
        queue.add("6");
        System.out.println(queue.get());
        queue.add("7");
        System.out.println(queue.get());
        queue.add("8");
        System.out.println(queue.get());
        queue.add("9");
        System.out.println("第六次" + queue.showQueue());
        System.out.println();
    }

}
